package com.dragon.datastructure.recursion;

/**
 * 删除单向链表中包含s的所有节点
 *
 * @author dragon
 * @since 2019/12/30
 */
public class SingleLinkedListRemoveElements {

    static class Node {
        int val;
        Node next;

        public Node(int val, Node next) {
            this.val = val;
            this.next = next;
        }

        public Node() {
        }

        @Override
        public String toString() {
            return "Node{" +
                    "val=" + val +
                    ", next=" + next +
                    '}';
        }
    }

    /**
     * 删除单向链表中包含s的所有节点
     *
     * @param head
     * @param s
     * @param depth 深度
     * @return
     */
    public static Node removeElements(Node head, int s, int depth) {
        String depthString = generateDepthString(depth);
        System.out.print(depthString);
        System.out.println("Call: remove " + s + " in " + (head == null ? null : head.val));
        if (head == null) {
            System.out.print(depthString);
            System.out.println("Return: null");
            return null;
        }
        Node node = removeElements(head.next, s, depth + 1);
        System.out.print(depthString);
        System.out.println("After remove " + s + ": " + (node == null ? null : node.val));

        Node ret;
        if (head.val == s) {
            ret = node;
        } else {
            head.next = node;
            ret = head;
        }
        System.out.print(depthString);
        System.out.println("Return: " + (ret == null ? null : ret.val));

        return ret;
    }

    private static String generateDepthString(int depth) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < depth; i++) {
            sb.append("--");
        }

        return sb.toString();
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 6, 2, 3, 6, 6};
        Node dummy = new Node();
        Node pre = dummy;
        for (int i = 0; i < nums.length; i++) {
            Node cur = new Node(nums[i], null);
            pre.next = cur;
            pre = cur;
        }

        Node ret = removeElements(dummy.next, 6, 0);
        System.out.println();
        while (ret != null) {
            System.out.print(ret.val + " ");
            ret = ret.next;
        }
    }

}
